#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int na=0; int nb=0;
        ListNode *p = headA;
        while(p!=NULL){
            ++na; p = p->next;
        }
        p = headB;
        while(p!=NULL){
            ++nb; p=p->next;
        }
        int ln = na; int sn = nb;
        ListNode *lhead = headA; ListNode *shead = headB;
        if(na < nb){
            ln = nb; sn = na;
            lhead = headB; shead = headA;
        }
        for(int i=0; i<ln-sn; ++i) lhead = lhead->next;
        for(int i=0; i<sn; ++i){
            if(lhead == shead) return lhead;
            lhead = lhead->next;
            shead = shead->next;
        }
        return NULL;
    }
};